package features.advance.leetcode.tree.easy;

import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import features.advance.leetcode.tree.model.TreeNode;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
 * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，
 * 又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
 */

/**
 * 剑指 Offer 54. 二叉搜索树的第k大节点
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 *
 *
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 *
 *
 * 限制：
 *
 * 1 ≤ k ≤ 二叉搜索树元素个数
 */

public class Offer54 {

    private static Logger log = LoggerFactory.getLogger(Offer54.class);

    /**
     * 解题思路：中序遍历倒序
     * @param root 要查找的树形结构数据
     * @param k 第k大
     * @return 要查找的目标值
     */
    public int kthLargest(TreeNode root, int k) {
        Map<String,Integer> res =new HashMap<>(16);
        res.put("k",k);
        dfs(root,res);
        return res.get("res");
    }

    public void dfs(TreeNode<Integer> node,Map<String, Integer> res){
        if (node == null) return;
        dfs(node.getRight(),res);
        if (res.get("k")==0)return;
        if(res.get("k") - 1 == 0 && res.get("k").equals(res.put("k", res.get("k") - 1))) {
            res.put("res",node.getVal());
        }
        dfs(node.getLeft(),res);
    }

    /**
     * 解析二叉查找树
     * @param arrStr
     * @return
     */
    public TreeNode<Integer> parseArray(String arrStr){
        List<Integer> integers = JSONArray.parseArray(arrStr, Integer.class);
        Map<Integer, TreeNode<Integer>> map = new HashMap<>(16);
        TreeNode<Integer> treeNode = new TreeNode<>();
        for (int i = integers.size() - 1; i >= 0; i--) {
            /*                   5
            1 3 4              3  |  6
            2 5 6             2|4  null|null
            3 7 8            1|null
            4 9 10
             */
            Integer integer = integers.get(i);
            if (integer !=null)  {
                treeNode = new TreeNode<>(integer);
                map.put(i,treeNode);
                if (map.get(i*2+1) !=null){
                    treeNode.setLeft(map.get(i*2+1));
                    map.remove(i*2+1);
                }
                if (map.get(i*2+2) !=null){
                    treeNode.setRight(map.get(i*2+2));
                    map.remove(i*2+2);
                }
            }
        }
        return treeNode;
    }

    public static void main(String[] args) {
        String jsonData = "{\"val\":\"3\",\"left\":{\"val\":1,\"right\":{\"val\":2}},\"right\":{\"val\":4}}";

        TreeNode<Integer> root = JSONObject.parseObject(jsonData, TreeNode.class);

        int k = 1;


        int answer = new Offer54() {
            @Override
            public int kthLargest(TreeNode root, int k) {
                return super.kthLargest(root, k);
            }

            ;
        }.kthLargest(root, k);


        log.info("方法返回值：{}", answer);

        String str = "[41,37,44,24,39,42,48,1,35,38,40,null,43,46,49,0,2,30,36,null,null,null,null,null,null,45,47,null,null,null,null,null,4,29,32,null,null,null,null,null,null,3,9,26,null,31,34,null,null,7,11,25,27,null,null,33,null,6,8,10,16,null,null,null,28,null,null,5,null,null,null,null,null,15,19,null,null,null,null,12,null,18,20,null,13,17,null,null,22,null,14,null,null,21,23]";
        TreeNode<Integer> treeNode = new Offer54() {
        }.parseArray(str);
        System.out.println(JSONObject.toJSONString(treeNode));


    }
}
